package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 思路:弄两个链表,一个比x小的,一个不比x小的,完了前面的末尾接上后面的开头
 *
 */

public class Q86 {

    public ListNode partition(ListNode head, int x) {
        ListNode formerHead = new ListNode(-1);
        ListNode former = formerHead;
        ListNode laterHead = new ListNode(-1);
        ListNode later = laterHead;
        ListNode curr = head;
        ListNode next = head;


        while (curr != null) {
            // 下面两行不能少
            next = curr.next;
            curr.next = null;
            if (curr.val < x) {
                former.next = curr;
                former = former.next;
            }
            else {
                later.next = curr;
                later = later.next;
            }
            curr = next;
        }
        former.next = laterHead.next;
        return formerHead.next;
    }

}
